package cn.hycat.leetcode.middle;

/**
 * @author 吕泽浩业
 * @version 1.0
 */
/*      Manacher算法
        给你一个字符串 s，找到 s 中最长的回文子串。

        示例 1：

        输入：s = "babad"
        输出："bab"
        解释："aba" 同样是符合题意的答案。
        示例 2：

        输入：s = "cbbd"
        输出："bb"*/
public class L5最长回文子串 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("aacabdkacaa"));
    }
    public static String longestPalindrome(String s) {
        //预处理 babad -> #b#a#b#a#d#
        char[] str = before(s);
        int index = 0;
        int ans = Integer.MIN_VALUE;
        int R = -1; //扩散的最右边
        int C= -1; //扩散的中心
        int[] pArr = new int[str.length];//扩散的半径
        for(int i = 0; i < str.length; i++) {
            pArr[i] = i >= R ? 1 : Math.min(pArr[2*C-i],R-i);
            while(i + pArr[i] < str.length && i - pArr[i] >= 0) {
                if(str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else break;
            }
            if(i + pArr[i] > R) {
                C = i;
                R = i + pArr[i];
            }
            if(pArr[i] > ans) {
                ans = pArr[i];
                index = i;
            }
        }
        System.out.println(str[17]);
        return after(str, index, ans);
    }

    public static char[] before(String s) {
        int index = 0;
        char[] chars = s.toCharArray();
        char[] res = new char[chars.length * 2 + 1];
        for(int i = 0; i < res.length; i++) {
            res[i] = i % 2 == 0 ? '#' : chars[index++];
        }
        return res;
    }

    public static String after(char[] str, int index, int ans) {
        StringBuilder builder = new StringBuilder();
        for(int i = index - ans + 1; i <= index + ans - 1; i++) {
            if(i % 2 == 1)
            builder.append(str[i]);
        }
        int[] a = {1,1};
        return builder.toString();
    }
}
